/**
* Sorting algoritms that sort vectors of type T
* void selectionSort(vector<T>& v);
* void insertionSort(vector<T>& v);
* void insertionSort(vector<T>& v, Compare comp);
* void radixSort(vector<int>& v, long d);
* void heapSort (vector<T>& v, Compare comp);
* void mergeSort(vector<T>& v);
* void quickSort(vector<T>& v);
*
* Defining the sorting interval the follwing notation is used
* [ start, stop ] means closed interval, begins at start and end with stop
* [ start, stop ) means closed, open interval, begins at start and end with stop-1
*
* class testPackage enables you to fill into three vectors random numbers as follows
*   create and store data as integers into three vectors:
*     v1: serie of random numbers (dubblets allowed)
*     v2: copy of v1 but sorted in ascending order (lowest first)
*     v3: copy of v1 but sorted in descending order (highest first)
*     count defines the number of integers to be generated. The sizes
*     of v1 and v2 and v3 will be count as well.
*     The interval of the generated random numbers is [0, max_rnd)
*     with default value n_rnd = 0x7FFFFFFF = 2147483647 = 2^31-1
*
* The algorithms are based on William Ford and William Torp, Data Structures with C++
* revised by Henrik Kold Mikkelsen, EIT
* Revision: 2005.12.08/1
**/

#ifndef SORTING_ALGORITHMS
#define SORTING_ALGORITHMS

#include <vector>
#include <queue>

#include "d_heap.h"	// heap function library
#include "d_random.h" // random generator library

using namespace std;

// class that creates a test suite of vectors of random numbers
class testPackage;

// sort a vector of type T using selection sort
template <typename T>
void selectionSort(vector<T>& v);

// sort a vector of type T using insertion sort
template <typename T>
void insertionSort(vector<T>& v);

// sort a vector of type T in ascending or descending order
// defined by the function object comp
template <typename T, typename Compare>
void insertionSort(vector<T>& v, Compare comp);

// sort v using the radix sort. d must have the highest value of numbers
void radixSort(vector<int>& v, long d);

// sort a vector using heapsort
template <typename T, typename Compare>
void heapSort (vector<T>& v, Compare comp);

// the elements in the ranges [first,mid) and [mid,last) are
// ordered. the function merges the ordered sequences into
// an ordered sequence in the range [first,last)
template <typename T>
void merge(vector<T>& v, int first, int mid, int last);

// sorts v in the index range [first,last) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v, int first, int last);

// sorts v in the index range [0,v.size()) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v);

// using the value at the midpoint of [first,last) as the pivot,
// locate the pivot in its final location so all elements
// to its left are <= to its value and all elements to the
// right are >= to its value. return the index of the pivot
template <typename T>
int pivotIndex(vector<T>& v, int first, int last);

// sort a vector using quicksort
template <typename T>
void quicksort(vector<T>& v, int first, int last);

// sort a vector using quicksort
template <typename T>
void quicksort(vector<T>& v);

// locate the kth largest element of v at index k
template <typename T>
void findK(vector<T>& v, int first, int last, int k);

// IMPLEMENTATIONS

template <typename T>
void selectionSort(vector<T>& v)
{
  // index of smallest item in each pass
  int smallIndex;
  // save the vector size in n
  int pass, j, n = v.size();
  T temp;

  // sort v[0]..v[n-2], and arr[n-1] is in place
  for (pass = 0; pass < n-1; pass++)
  {
    // start the scan at index pass; set smallIndex to pass
    smallIndex = pass;
    // j scans the sublist v[pass+1]..v[n-1]
    for (j = pass+1; j < n; j++)
      // update smallIndex if smaller element is found
      if (v[j] < v[smallIndex])
        smallIndex = j;
    // when finished, place smallest item in arr[pass]
    if (smallIndex != pass)
    {
      temp = v[pass];
      v[pass] = v[smallIndex];
      v[smallIndex] = temp;
    }
  }
}

template <typename T>
void insertionSort(vector<T>& v)
{
  int i, j, n = v.size();
  T target;

  // place v[i] into the sublist
  //   v[0] ... v[i-1], 1 <= i < n,
  // so it is in the correct position
  for (i = 1; i < n; i++)
  {
    // index j scans down list from v[i] looking for
    // correct position to locate target. assigns it to
    // v[j]
    j = i;
    target = v[i];
    // locate insertion point by scanning downward as long
    // as target < v[j-1] and we have not encountered the
    // beginning of the list
    while (j > 0 && target < v[j-1])
    {
      // shift elements up list to make room for insertion
      v[j] = v[j-1];
      j--;
    }
    // the location is found; insert target
    v[j] = target;
  }
}

template <typename T, typename Compare>
void insertionSort(vector<T>& v, Compare comp)
{
  int i, j, n = v.size();
  T target;

  // place v[i] into the sublist
  //   v[0] ... v[i-1], 1 <= i < n,
  // so it is in the correct position
  for (i = 1; i < n; i++)
  {
    // index j scans down list from v[i] looking for
    // correct position to locate target. assigns it to
    // v[j]
    j = i;
    target = v[i];
    // locate insertion point by scanning downward as long
    // as target < v[j-1] and we have not encountered the
    // beginning of the list
    while (j > 0 && comp(target, v[j-1]))
    {
      // shift elements up list to make room for insertion
      v[j] = v[j-1];
      j--;
    }
    // the location is found; insert target
    v[j] = target;
  }
}

// support function for radixSort()
// distribute vector elements into one of 10 queues
// using the digit corresponding to power
//   power = 1    ==> 1's digit
//   power = 10   ==> 10's digit
//   power = 100  ==> 100's digit
//   ...
void distribute(const vector<int>& v, queue<int> digitQueue[],
                int power)
{
  int i;

  // loop through the vector, inserting each element into
  // the queue (v[i] / power) % 10
  for (i = 0; i < v.size(); i++)
    digitQueue[(v[i] / power) % 10].push(v[i]);
}

// support function for radixSort()
// gather elements from the queues and copy back to the vector
void collect(queue<int> digitQueue[], vector<int>& v)
{
  int i = 0, digit;

  // scan the vector of queues using indices 0, 1, 2, etc.
  for (digit = 0; digit < 10; digit++)
    // collect items until queue empty and copy items back
    // to the vector
    while (!digitQueue[digit].empty())
    {
      v[i] = digitQueue[digit].front();
      digitQueue[digit].pop();
      i++;
    }
}

void radixSort(vector<int>& v, long d)
{
  // calc. number of digits
  long num = d - 1;
  int n_radix;
  // calculate number of digits in d
  for (n_radix = 0; num != 0; n_radix++)
    num /= 10;

  int i;
  int power = 1;
  queue<int> digitQueue[10];

  for (i=0; i < n_radix; i++)
  {
    distribute(v, digitQueue, power);
    collect(digitQueue, v);
    power *= 10;
  }
}

template <typename T, typename Compare>
void heapSort (vector<T>& v, Compare comp)
{
  // "heapify" the vector v
  makeHeap(v, comp);

  int i, n = v.size();

  // iteration that determines elements v[n-1] ... v[1]
  for(i = n; i > 1;i--)
  {
    // call popHeap() to move next largest to v[n-1]
    popHeap(v, i, comp);
  }
}

template <typename T>
void merge(vector<T>& v, int first, int mid, int last)
{
  // temporary vector to merge the sorted sublists
  vector<T> tempVector;
  int indexA, indexB, indexV;

  // set indexA to scan sublistA (index range [first,mid)
  // and indexB to scan sublistB (index range [mid, last)
  indexA = first;
  indexB = mid;

  // while both sublists are not exhausted, compare v[indexA] and
  // v[indexB]copy the smaller to vector temp using push_back()
  while (indexA < mid && indexB < last)
    if (v[indexA] < v[indexB])
    {
      tempVector.push_back(v[indexA]);	// copy element to temp
      indexA++;								// increment indexA
    }
    else
    {
      tempVector.push_back(v[indexB]);	// copy element to temp
      indexB++;								// increment indexB
    }

    // copy the tail of the sublist that is not exhausted
    while (indexA < mid)
    {
      tempVector.push_back(v[indexA]);
      indexA++;
    }

    while (indexB < last)
    {
      tempVector.push_back(v[indexB]);
      indexB++;
    }

    // copy vector tempVector using indexV to vector v using indexA
    // which is initially set to first
    indexA = first;

    // copy elements from temporary vector to original list
    for (indexV = 0; indexV < tempVector.size(); indexV++)
    {
      v[indexA] = tempVector [indexV];
      indexA++;
    }
}

// sorts v in the index range [first,last) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v, int first, int last)
{
  // if the sublist has more than 1 element continue
  if (first + 1 < last)
  {
    // for sublists of size 2 or more, call mergeSort()
    // for the left and right sublists and then
    // merge the sorted sublists using merge()
    int midpt = (last + first) / 2;

    mergeSort(v, first, midpt);
    mergeSort(v, midpt, last);
    merge(v, first, midpt, last);
  }
}

// sorts v in the index range [0,v.size()) by merging
// ordered sublists
template <typename T>
void mergeSort(vector<T>& v)
{
  mergeSort(v, 0, v.size());
}


template <typename T>
int pivotIndex(vector<T>& v, int first, int last)
{
  // index for the midpoint of [first,last) and the
  // indices that scan the index range in tandem
  int mid, scanUp, scanDown;
  // pivot value and object used for exchanges
  T pivot, temp;

  if (first == last)
    return last;
  else if (first == last-1)
    return first;
  else
  {
    mid = (last + first)/2;
    pivot = v[mid];

    // exchange the pivot and the low end of the range
    // and initialize the indices scanUp and scanDown.
    v[mid] = v[first];
    v[first] = pivot;

    scanUp = first + 1;
    scanDown = last - 1;

    // manage the indices to locate elements that are in
    // the wrong sublist; stop when scanDown <= scanUp
    for(;;)
    {
      // move up lower sublist; stop when scanUp enters
      // upper sublist or identifies an element >= pivot
      while (scanUp <= scanDown && v[scanUp] < pivot)
        scanUp++;

      // scan down upper sublist; stop when scanDown locates
      // an element <= pivot; we guarantee we stop at arr[first]
      while (pivot < v[scanDown])
        scanDown--;

      // if indices are not in their sublists, partition complete
      if (scanUp >= scanDown)
        break;

      // indices are still in their sublists and identify
      // two elements in wrong sublists. exchange
      temp = v[scanUp];
      v[scanUp] = v[scanDown];
      v[scanDown] = temp;

      scanUp++;
      scanDown--;
    }

    // copy pivot to index (scanDown) that partitions sublists
    // and return scanDown
    v[first] = v[scanDown];
    v[scanDown] = pivot;
    return scanDown;
  }
}

template <typename T>
void quicksort(vector<T>& v, int first, int last)
{
  // index of the pivot
  int pivotLoc;
  // temp used for an exchange when [first,last) has
  // two elements
  T temp;

  // if the range is not at least two elements, return
  if (last - first <= 1)
    return;

  // if sublist has two elements, compare v[first] and
  // v[last-1] and exchange if necessary
  else if (last - first == 2)
  {
    if (v[last-1] < v[first])
    {
      temp = v[last-1];
      v[last-1] = v[first];
      v[first] = temp;
    }
    return;
  }
  else
  {
    pivotLoc = pivotIndex(v, first, last);

    // make the recursive call
    quicksort(v, first, pivotLoc);

    // make the recursive call
    quicksort(v, pivotLoc +1, last);
  }
}

// sort a vector using quicksort
template <typename T>
void quicksort(vector<T>& v)
{
  quicksort(v, 0, v.size()- 1);
}

template <typename T>
void findK(vector<T>& v, int first, int last, int k)
{
  int index;

  // partition range [first,last) in v about the
  // pivot v[index]
  index = pivotIndex(v, first, last);

  // if index == k, we are done. kth largest is v[k]
  if (index == k)
    return;
  else if(k < index)
    // search in lower sublist [first,index)
    findK(v, first, index, k);
  else
    // search in upper sublist [index+1,last)
    findK(v, index+1, last, k);
}

class testPackage
{
public:
  testPackage(vector<int>& v1, vector<int>& v2, vector<int>& v3,
    int count);
  testPackage(vector<int>& v1, vector<int>& v2, vector<int>& v3,
    int count, long n_rnd);
  void createBasis(vector<int>& v1, vector<int>& v2, vector<int>& v3,
    int count, long n_rnd);
  long highVal();
private:
  randomNumber rnd;
};

testPackage::testPackage(vector<int>& v1, vector<int>& v2, vector<int>& v3, int count)
{
  createBasis(v1, v2, v3, count, rnd.highVal());
}

testPackage::testPackage(vector<int>& v1, vector<int>& v2, vector<int>& v3,
                         int count, long n_rnd)
{
  createBasis(v1, v2, v3, count, n_rnd);
}

// create and store data as integers into three vectors:
// v1: serie of random numbers (dubblets allowed)
// v2: copy of v1 but sorted in ascending order (lowest first)
// v3: copy of v1 but sorted in descending order (highest first)
// count defines the number of integers to be generated. The sizes
// of v1 and v2 and v3 will be count as well.
// The interval of the generated random numbers is [0, max_rnd)
// with default value n_rnd = 0x7FFFFFFF = 2147483647 = 2^31-1
void testPackage::createBasis(vector<int>& v1, vector<int>& v2, vector<int>& v3,
                              int count, long n_rnd)
{
  int i, j;

  v1.resize(count);
  v2.resize(count);
  v3.resize(count);

  randomNumber r_num;

  for (i = 0; i < count; i++)
  {
    v1[i] = v2[i] = r_num.random(n_rnd);
  }
  // v1 and v2 holds random numbers

  quicksort(v2, 0, count); // v2 holds ascending numbers

  for (i = 0, j = count - 1; i < count; i++, j--)
    v3[i] = v2[j]; // v3 holds descending numbers
}

long testPackage::highVal()
{
  return rnd.highVal();
}

#endif   // SORTING_ALGORITHMS
